SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Frequent subtree mining</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Frequent subtree mining</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Computer_science" title="Computer science">computer science</a>, <b>frequent subtree mining</b> is the problem of finding all patterns in a given database whose support (a metric related to its number of occurrences in other subtrees) is over a given threshold.<sup id="cite_ref-Chi01_1-0" class="reference"><a href="#cite_note-Chi01-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It is a more general form of the <a href="Maximum_agreement_subtree_problem" title="Maximum agreement subtree problem">maximum agreement subtree problem</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Frequent subtree mining is the problem of trying to find all of the patterns whose "support" is over a certain user-specified level, where "support" is calculated as the number of trees in a database which have at least one subtree <a href="Graph_isomorphism" title="Graph isomorphism">isomorphic</a> to a given pattern.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Formal_definition">Formal definition</h3></div>

<p>The problem of frequent subtree mining has been formally defined as:<sup id="cite_ref-Chi01_1-1" class="reference"><a href="#cite_note-Chi01-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<dl><dd>Given a threshold <i>minfreq</i>, a class of trees <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./e7b3edab7022ca9e2976651bc59c489513ee9019.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.239ex; height:2.176ex;" alt="{\displaystyle {\mathcal {C}}}" loading="lazy"></span>, a transitive subtree relation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\preceq T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\preceq T}</annotation>

</semantics>

</math></span><img src="./3cecd0370b75586d94f4db799a82046362013623.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.48ex; height:2.343ex;" alt="{\displaystyle P\preceq T}" loading="lazy"></span> between trees <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P,T\in {\mathcal {C}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P,T\in {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./b6c89b34958b4a641c81e42217d54c4b9a369d86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.495ex; height:2.509ex;" alt="{\displaystyle P,T\in {\mathcal {C}}}" loading="lazy"></span>, a finite set of trees <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}\subseteq {\mathcal {C}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}\subseteq {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./1c7b85fc3d3a70b7b24211007e97d6f2fc399bb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.129ex; height:2.343ex;" alt="{\displaystyle {\mathcal {D}}\subseteq {\mathcal {C}}}" loading="lazy"></span>, the frequent subtree mining problem is the problem of finding all trees <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}\subset {\mathcal {C}}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}\subset {\mathcal {C}}}</annotation>

</semantics>

</math></span><img src="./dd9c07bd2bd6f446dbcef6053345a72e956342a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.041ex; height:2.176ex;" alt="{\displaystyle {\mathcal {P}}\subset {\mathcal {C}}}" loading="lazy"></span> such that no two trees in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {P}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {P}}}</annotation>

</semantics>

</math></span><img src="./10d6ec962de5797ba4f161c40e66dca74ae95cc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.704ex; height:2.176ex;" alt="{\displaystyle {\mathcal {P}}}" loading="lazy"></span> are isomorphic and

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall P\in {\mathcal {P}}:\quad \mathrm {freq} (P,{\mathcal {D}})=\sum \nolimits _{T\in {\mathcal {D}}}d(P,T)\geq \mathrm {minfreq} ,}</annotation>

</semantics>

</math></span><img src="./bcecffc0188cef2190e42f5434b4378564718483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.505ex; width:51.983ex; height:4.009ex;" alt="{\displaystyle \forall P\in {\mathcal {P}}:\quad \mathrm {freq} (P,{\mathcal {D}})=\sum \nolimits _{T\in {\mathcal {D}}}d(P,T)\geq \mathrm {minfreq} ,}" loading="lazy"></span></dd></dl></dd>

<dd>where <span class="texhtml mvar" style="font-style:italic;">d</span> is an anti-monotone function such that if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P'\preceq P}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P'\preceq P}</annotation>

</semantics>

</math></span><img src="./3edd9f62c98aa2e83b0e3ef7111cb6dab4fea53e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.35ex; height:2.676ex;" alt="{\displaystyle P'\preceq P}" loading="lazy"></span> then

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall T\in {\mathcal {C}}:\quad d(P',T)\geq d(P,T).}</annotation>

</semantics>

</math></span><img src="./7ea0bbd62670f00d14326817bb14054188428c6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.656ex; height:3.009ex;" alt="{\displaystyle \forall T\in {\mathcal {C}}:\quad d(P',T)\geq d(P,T).}" loading="lazy"></span></dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="TreeMiner">TreeMiner</h2></div>

<p>In 2002, Mohammed J. Zaki introduced TreeMiner, an efficient algorithm for solving the frequent subtree mining problem, which used a "scope list" to represent tree nodes and which was contrasted with PatternMatcher, an algorithm based on pattern matching.<sup id="cite_ref-:0_4-0" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Definitions">Definitions</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Induced_sub-trees">Induced sub-trees</h4></div>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=(V_{s},E_{s})}</annotation>

</semantics>

</math></span><img src="./d7f3ed3dae9b173e68b5ca59db0ed6e31c293fa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.518ex; height:2.843ex;" alt="{\displaystyle S=(V_{s},E_{s})}" loading="lazy"></span> is an induced sub-tree of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=(V,E)}</annotation>

</semantics>

</math></span><img src="./d92d5a4adcb93751dbecb1cddfc0a254b9488f9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.141ex; height:2.843ex;" alt="{\displaystyle T=(V,E)}" loading="lazy"></span> if and only if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{s}\subseteq V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{s}\subseteq V}</annotation>

</semantics>

</math></span><img src="./c25bb5e964a1ed44f14addf6c41fc8b24208366d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.244ex; height:2.509ex;" alt="{\displaystyle V_{s}\subseteq V}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{s}\subseteq E}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E_{s}\subseteq E}</annotation>

</semantics>

</math></span><img src="./4903101cf2745a20813b428a6bf209c4d08440e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.593ex; height:2.509ex;" alt="{\displaystyle E_{s}\subseteq E}" loading="lazy"></span>. In other words, any two nodes in S that are directly connected by an edge is also directly connected in T. For any node A and B in S, if node A is the parent of node B in S, then node A must also be the parent of node B in T.

</p>

<div class="mw-heading mw-heading4"><h4 id="Embedded_sub-trees">Embedded sub-trees</h4></div>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=(V_{s},E_{s})}</annotation>

</semantics>

</math></span><img src="./d7f3ed3dae9b173e68b5ca59db0ed6e31c293fa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.518ex; height:2.843ex;" alt="{\displaystyle S=(V_{s},E_{s})}" loading="lazy"></span> is an embedded sub-tree of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=(V,E)}</annotation>

</semantics>

</math></span><img src="./d92d5a4adcb93751dbecb1cddfc0a254b9488f9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.141ex; height:2.843ex;" alt="{\displaystyle T=(V,E)}" loading="lazy"></span> if and only if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{s}\subseteq V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{s}\subseteq V}</annotation>

</semantics>

</math></span><img src="./c25bb5e964a1ed44f14addf6c41fc8b24208366d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.244ex; height:2.509ex;" alt="{\displaystyle V_{s}\subseteq V}" loading="lazy"></span> and two endpoint nodes of any edge in S are on the same path from the root to a leaf node in T. In other words, for any node A and B in S, if node A is the parent of node B in S, then node A must be an ancestor of node B in T. Any induced sub-trees are also embedded sub-trees, and thus the concept of embedded sub-trees is a generalization of induced sub-trees. As such embedded sub-trees characterizes the hidden patterns in a tree that are missing in traditional induced sub-tree mining. A sub-tree of size k is often called a k-sub-tree.

</p>

<div class="mw-heading mw-heading4"><h4 id="Support">Support</h4></div>

<p>The support of a sub-tree is the number of trees in a database that contains the sub-tree. A sub-tree is frequent if its support is not less than a user-specified threshold (often denoted as <i>minsup).</i> The goal of TreeMiner is to find all embedded sub-trees that have support at least the minimum support.

</p>

<div class="mw-heading mw-heading4"><h4 id="String_representation_of_trees">String representation of trees</h4></div>

<p>There are several different ways of encoding a tree structure. TreeMiner uses string representations of trees for efficient tree manipulation and support counting. Initially the string is set to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varnothing }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varnothing }</annotation>

</semantics>

</math></span><img src="./00595c5e33692e724937fdcc8870496acce1ac74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.009ex;" alt="{\displaystyle \varnothing }" loading="lazy"></span>. Starting from the root of the tree, node labels are added to the string in depth-first search order. -1 is added to the string whenever the search process backtracks from a child to its parent. For example, a simple binary tree with root labelled A, a left child labelled B and right child labelled C can be represented by a string A B -1 C -1.

</p>

<div class="mw-heading mw-heading4"><h4 id="Prefix_equivalence_class">Prefix equivalence class</h4></div>

<p>Two k-sub-trees are said to be in the same prefix equivalence class if the string representation of them are identical up to the (k-1)-th node. In other words, all elements in a prefix equivalence class only differ by the last node. For example, two trees with string representation A B -1 C -1 and A B -1 D -1 are in the prefix equivalence class A B with elements (C, 0) and (D,0). An element of a prefix class is specified by the node label paired with the 0-based depth first index of the node it is attached to. In this example, both elements of prefix class A B are attached to the root, which has an index of 0.

</p>

<div class="mw-heading mw-heading4"><h4 id="Scope">Scope</h4></div>

<p>The scope of a node A is given by a pair of numbers <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [l,r]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [l,r]}</annotation>

</semantics>

</math></span><img src="./be45874f852a2b7bfa2df52888aaec6919238623.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.07ex; height:2.843ex;" alt="{\displaystyle [l,r]}" loading="lazy"></span> where l and r are the minimum and maximum node index in the sub-tree rooted at A. In other words, l is the index of A, and r is the index of the rightmost leaf among the descendants of A. As such the index of any descendant of A must lie in the scope of A, which will be a very useful property when counting the support of sub-trees.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithm">Algorithm</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Candidate_generation">Candidate generation</h4></div>

<p>Frequent sub-tree patterns follow the anti-monotone property. In other words, the support of a k-sub-tree is less than or equal to the support of its (k-1)-sub-trees. Only super patterns of known frequent patterns can possibly be frequent. By utilizing this property, k-sub-trees candidates can be generated based on frequent (k-1)-sub-trees through prefix class extension. Let C be a prefix equivalence class with two elements (x,i) and (y,j). Let C' be the class representing the extension of element (x,i). The elements of C' are added by performing <i>join</i> operation on the two (k-1)-sub-trees in C. The <i>join</i> operation on (x,i) and (y,j) is defined as the following.

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i>j}</annotation>

</semantics>

</math></span><img src="./2886c2c870767297c5efcf319aa2bf68a31cb4b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i>j}" loading="lazy"></span>, then add (y,j) to C'.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=j}</annotation>

</semantics>

</math></span><img src="./706e0928b2bf0f24076b0c90bb20616ff2068343.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i=j}" loading="lazy"></span>, then add (y,j) and (y, ni) to C' where ni the depth-first index of x in C</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i<j}</annotation>

</semantics>

</math></span><img src="./e60ff2d1b23e30fb2979e8c1536da03493f943cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i<j}" loading="lazy"></span>, no possible element can be added to C'</li></ul>

<p>This operation is repeated for any two ordered, but not necessarily distinct elements in C to construct the extended prefix classes of k-sub-trees.

</p>

<div class="mw-heading mw-heading4"><h4 id="Scope-list_representation">Scope-list representation</h4></div>

<p>TreeMiner performs depth first candidate generation using scope-list representation of sub-trees to facilitate faster support counting. A k-sub-tree S can be representation by a triplet (t,m,s) where t is the tree id the sub-tree comes from, m is the prefix match label, and s the scope of the last node in S. Depending on how S occurs in different trees across the database, S can have different scope-list representation. TreeMiner defines <i>scope-list join</i> that performs class extension on scope-list representation of sub-trees. Two elements (x,i) and (y,j) can be joined if there exists two sub-trees <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (t_{x},m_{x},s_{x})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (t_{x},m_{x},s_{x})}</annotation>

</semantics>

</math></span><img src="./542ee718961024f5cace18f4aac8b490aee5131b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.365ex; height:2.843ex;" alt="{\displaystyle (t_{x},m_{x},s_{x})}" loading="lazy"></span>and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (t_{y},m_{y},s_{y})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (t_{y},m_{y},s_{y})}</annotation>

</semantics>

</math></span><img src="./9aac0654b6ad279972357b09629ab3d08e9924d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.996ex; height:3.009ex;" alt="{\displaystyle (t_{y},m_{y},s_{y})}" loading="lazy"></span> that satisfy either of the following conditions.

</p>

<ul><li>In-scope test: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}}</annotation>

</semantics>

</math></span><img src="./3ec1205a664e30f2b28657637a74f1b0ad31bbf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.97ex; height:2.676ex;" alt="{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}}" loading="lazy"></span>, which corresponds to the case when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=j}</annotation>

</semantics>

</math></span><img src="./706e0928b2bf0f24076b0c90bb20616ff2068343.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i=j}" loading="lazy"></span>.</li>

<li>Out-scope test: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}}</annotation>

</semantics>

</math></span><img src="./96b5ddcd794f4e9b5d5043858a8d9b4861d13e85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.97ex; height:2.676ex;" alt="{\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}}" loading="lazy"></span>, which correspond to the case when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i>j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i>j}</annotation>

</semantics>

</math></span><img src="./2886c2c870767297c5efcf319aa2bf68a31cb4b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.859ex; height:2.509ex;" alt="{\displaystyle i>j}" loading="lazy"></span>.</li></ul>

<p>By keeping track of distinct tree ids used in the scope-list tests, the support of sub-trees can be calculated efficiently.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Domains in which frequent subtree mining is useful tend to involve complex relationships between data entities: for instance, the analysis of XML documents often requires frequent subtree mining.<sup id="cite_ref-Chi01_1-2" class="reference"><a href="#cite_note-Chi01-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Another domain where this is useful is the web usage mining problem: since the actions taken by users when visiting a web site can be recorded and categorized in many different ways, complex databases of trees need to be analyzed with frequent subtree mining.<sup id="cite_ref-:0_4-1" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Other domains in which frequent subtree mining is useful include <a href="Computational_biology" title="Computational biology">computational biology</a>,<sup id="cite_ref-Dee13_5-0" class="reference"><a href="#cite_note-Dee13-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Yun05_6-0" class="reference"><a href="#cite_note-Yun05-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> RNA structure analysis,<sup id="cite_ref-Yun05_6-1" class="reference"><a href="#cite_note-Yun05-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> pattern recognition,<sup id="cite_ref-Chi04_7-0" class="reference"><a href="#cite_note-Chi04-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> bioinformatics,<sup id="cite_ref-Xia03_8-0" class="reference"><a href="#cite_note-Xia03-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> and analysis of the <a href="KEGG" title="KEGG">KEGG</a> GLYCAN database.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Challenges">Challenges</h2></div>

<p>Checking whether a pattern (or a transaction) supports a given subgraph is an <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> problem, since it is an NP-complete instance of the <a href="Subgraph_isomorphism_problem" title="Subgraph isomorphism problem">subgraph isomorphism problem</a>.<sup id="cite_ref-Chi04_7-1" class="reference"><a href="#cite_note-Chi04-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Furthermore, due to <a href="Combinatorial_explosion" title="Combinatorial explosion">combinatorial explosion</a>, according to Lei et al., "mining all frequent subtree patterns becomes infeasible for a large and dense tree database".<sup id="cite_ref-Zou06_10-0" class="reference"><a href="#cite_note-Zou06-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChiMuntzNijssenKok2005" class="citation journal cs1">Chi, Yun; Muntz, Richard R.; Nijssen, Siegfried; Kok, Joost N. (28 June 2005). "Frequent Subtree Mining - An Overview". <i>Fundamenta Informaticae</i>. <b>66</b>: <span class="nowrap">161–</span>198. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14827585">14827585</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFDeepakFernández-BacaTirthapuraSanderson2013" class="citation journal cs1">Deepak, Akshay; Fernández-Baca, David; Tirthapura, Srikanta; Sanderson, Michael J.; McMahon, Michelle M. (July 2013). <a rel="nofollow" class="external text" href="http://lib.dr.iastate.edu/cs_techreports/11">"EvoMiner: frequent subtree mining in phylogenetic databases"</a>. <i>Knowledge and Information Systems</i>. <b>41</b> (3): <span class="nowrap">559–</span>590. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10115-013-0676-0">10.1007/s10115-013-0676-0</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:254145982">254145982</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Dai, H., Srikant, R. and Zhang, C. (2004). "<a rel="nofollow" class="external text" href="https://link.springer.com/book/10.1007%2Fb97861">Advances in Knowledge Discovery and Data Mining.</a>" <i>8th Pacific-Asia Conference, PAKDD 2004, Sydney, Australia, May 26–28, 2004, Proceedings</i>. 1st ed. p. 65.</span>

</li>

<li id="cite_note-:0-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFZaki2002" class="citation book cs1">Zaki, Mohammed J. (2002). <a rel="nofollow" class="external text" href="https://dl.acm.org/citation.cfm?id=775058">"Efficiently mining frequent trees in a forest"</a>. <i>Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining</i>. pp. <span class="nowrap">71–</span>80. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F775047.775058">10.1145/775047.775058</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1581135671</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1649653">1649653</a><span class="reference-accessdate">. Retrieved <span class="nowrap">16 June</span> 2014</span>.</cite></span>

</li>

<li id="cite_note-Dee13-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Dee13_5-0">^</a></b></span> <span class="reference-text">Deepak, Akshay, David Fernández-Baca, Srikanta Tirthapura, Michael J. Sanderson, and Michelle M. McMahon. "<a rel="nofollow" class="external text" href="https://link.springer.com/article/10.1007/s10115-013-0676-0">EvoMiner: frequent subtree mining in phylogenetic databases</a>." Knowledge and Information Systems (2011): 1-32.</span>

</li>

<li id="cite_note-Yun05-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-Yun05_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Yun05_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Chi, Yun, Yirong Yang, and Richard R. Muntz. "<a rel="nofollow" class="external text" href="https://link.springer.com/article/10.1007/s10115-004-0180-7">Canonical forms for labelled trees and their applications in frequent subtree mining</a>." <i>Knowledge and Information Systems</i> 8, no. 2 (2005): 203–234.</span>

</li>

<li id="cite_note-Chi04-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-Chi04_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Chi04_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFChiYangMuntz2004" class="citation journal cs1">Chi, Yun; Yang, Yirong; Muntz, Richard R. (2004). <a rel="nofollow" class="external text" href="http://www.cs.ucla.edu/tech-report/2003-reports/030043.pdf">"Mining Frequent Rooted Trees and Free Trees Using Canonical Forms"</a> <span class="cs1-format">(PDF)</span>. <i>Knowledge and Information Systems</i><span class="reference-accessdate">. Retrieved <span class="nowrap">16 June</span> 2014</span>.</cite></span>

</li>

<li id="cite_note-Xia03-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Xia03_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFXiaoYaoLiDunham2003" class="citation conference cs1">Xiao, Yongqiao; Yao, Jenq-Foung; Li, Zhigang; Dunham, Margaret H. (2003). "Efficient data mining for maximal frequent subtrees". <i>Third IEEE International Conference on Data Mining</i>. ICDM 2003. pp. <span class="nowrap">379–</span>386. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICDM.2003.1250943">10.1109/ICDM.2003.1250943</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFAoki-Kinoshita2009" class="citation book cs1">Aoki-Kinoshita, Kiyoko F. (2009). <i>Glycome Informatics: Methods and Applications</i>. CRC Press. p. 141. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781420083347</bdi>.</cite></span>

</li>

<li id="cite_note-Zou06-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-Zou06_10-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFZouLuZhangHu2006" class="citation conference cs1">Zou, Lei; Lu, Yansheng; Zhang, Huaming; Hu, Rong (2006). "Mining Frequent Induced Subtree Patterns with Subtree-Constraint". <i>Sixth IEEE International Conference on Data Mining Workshops</i>. ICDM Workshops 2006. pp. <span class="nowrap">3–</span>7. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FICDMW.2006.112">10.1109/ICDMW.2006.112</a>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-03-09" href="https://en.wikipedia.org/wiki/?title=Frequent_subtree_mining&oldid=1212808351">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>